1. [Field of the Invention]
The present invention relates to an encoder and decoder for correcting an error in Reed-Solomon (RS) codes.
2. [Description of the Prior Art]
There is known a decoder using a Euclid's decoding method for decoding the RS, BCH, or Goppa codes. The Euclid's decoding method was discovered by Sugiyama et al in 1974 (Sugiyama, Kasahara, Hirasawa, and Suberikawa, "Discussion of the Goppa Code," Electronic Communications Society Technical Study Report, PRL 73-77, pp 11-20 (1974)). The Goppa code is a broad class of new linear codes defined by a remarkable technique for projecting code vectors to rational equations including a subclass of the BCH code. Of course, it is applicable to the RS code. This Euclid's decoding method is easier to solve than Peterson' algorithm and is much easier to understand than Berlekamp's algorithm.
The decoding of an RS code consists of the following four steps:
(1) Finding the syndrome.
(2) Finding an error locator polynomial and an error evaluator polynomial from the syndrome.
(3) Determining an error location from the error locator polynomial using Chien's algorithm.
(4) Determining an error value from the error evaluator polynomial.
Euclid's algorithm is used in the above step 2. In the Euclid's decoding method of Goppa codes, the syndrome polynomial is defined by ##EQU3## where .alpha.i is an element of GF(q) which is different for i and G(z) is a Goppa polynomial that satisfies ##EQU4## where ai is an element of GF(q). For RS codes, EQU G(z)=Z.sup.2t
where t is the number of correctable errors and is related to the minimum distance d as follows EQU t=[(d-1)/2]
The Gaussian symbol [x] represents the maximum integer no greater than x. For RS codes, Eq. 1 becomes ##EQU5## Let us find a syndrome Sj (j=0, 1, . . . 2t-1) from the received vector. If the received vector r(X)=r1+r2X+ . . . +rnX.sup.n-1, the error vector e(X)=e1+e2X+ . . . enX.sup.n-1, and the roots of a generation polynomial g(X)=.alpha..sup..gamma., .alpha..sup..gamma.+1, . . . .alpha..sup..gamma.+i-2, then ##EQU6## Let us now consider the relation between Sj and S(z). If .gamma.=1, then S(z) is given by ##EQU7## On the other hand, Eq. 3 can be transformed as follows ##EQU8## By converting (2t-1-j) to j in Eq. 7, we obtain ##EQU9## By comparing Eqs. 6 and 8, we obtain EQU .alpha..sub.i.sup.-(j+1) =.alpha..sup.(j+1)(i-1) ( 9)
Hence, S(z) can be given by Sj. EQU .alpha..sub.i.sup.-1 =.alpha..sup.i-1 ( 10)
From the above relationship, Eq. 3 is given by ##EQU10## Next, Eq. 3 is transformed as follows ##EQU11## Let E be a set of error locations (i is a member thereof and ei.noteq.0), and ##EQU12## then, Eq. 13 becomes ##EQU13## Eq. 17 is called key equation and cannot generally be solved. However, when the number of errors e is less than t, each error pattern has one different syndrome polynomial so that .eta.(z) and .sigma.(z) can unequivocally be determined from S(z).
FIG. 13 shows a flowchart for determining a solution of the key equation using Euclid's algorithm. The symbol [.multidot.] means a quotient of division. From Eq. 14, the error locator polynomial .sigma.(z) is ##EQU14## By substituting locations .alpha.1 to .alpha.n in .tau.(z), we obtain an error location .alpha.i given by EQU .sigma.(.alpha..sub.i)=0 (19)
This method is called Chien's algorithm. The error value ei at the error loaction i will be determined from the error locator polynomial .sigma.(z) obtained from Euclid's algorithm, the error evaluator polynomial .eta.(z), and the error location i obtained from Chien's algorithm. From Eqs. 14 and 15, ##EQU15## By performing formal differentiation for Eq. 20, we obtain ##EQU16## By substituting the error location .alpha.i for z in Eq. 22, we obtain ##EQU17## Similarly to Eq. 22, by substituting .alpha.i in Eq. 23, we obtain ##EQU18## From Eqs. 23 and 24, the error value is determined by EQU ei=.eta.(.alpha.i)/.sigma.(.alpha.i).
If the error is a single error, the error value is given by EQU ei=.eta.(z) and deg. .eta.(z)=0. (26)
For example, let us decode a RS code (15, 7, 9) on GF(2.sup.8) using the Euclid decoding method. Let the primitive polynomial p(X) and the generator polynomial g(X) be: ##EQU19## and the transmitted vector v and the received vector r be v=(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
r=(0, 0, .alpha..sup.79, .alpha..sup.88, .alpha..sup.175, .alpha..sup.3, 0, 0, 0, 0, 0, 0, 0, 0, 0). PA1 M1.rarw.Z.sup.8 PA1 M2(z).rarw.S(z) PA1 U1(z).rarw.0 PA1 U2(z).rarw.0 PA1 U1'(z).rarw..alpha..sup.0 PA1 M1(z).rarw.M2(z) PA1 M2(z).rarw.R(z) PA1 U1'(z).rarw.U1(z) PA1 .alpha..sub.3 .fwdarw..alpha..sup.253, .alpha..sub.4 .fwdarw..alpha..sup.252, .alpha..sub.5 .fwdarw..alpha..sup.251, .alpha..sub.6 .fwdarw..alpha..sup.250,
The syndromes S0 to S7 for the received vector are given by EQU S0=.alpha..sup.81 +.alpha..sup.91 +.alpha..sup.179 +.alpha..sup.8 =.alpha..sup.224 ( 29) EQU S1=.alpha..sup.83 +.alpha..sup.94 +.alpha..sup.183 +.alpha..sup.13 =.alpha..sup.74 ( 30) EQU S2=.alpha..sup.85 +.alpha..sup.97 +.alpha..sup.187 +.alpha..sup.18 =.alpha..sup.103 ( 31) EQU S3=.alpha..sup.87 +.alpha..sup.100 +.alpha..sup.191 +.alpha..sup.23 =.alpha..sup.160 ( 32) EQU S4=.alpha..sup.89 +.alpha..sup.103 +.alpha..sup.195 +.alpha..sup.28 =.alpha..sup.141 ( 33) EQU S5=.alpha..sup.91 +.alpha..sup.106 +.alpha..sup.199 +.alpha..sup.33 =.alpha..sup.65 ( 34) EQU S6=.alpha..sup.93 +.alpha..sup.109 +.alpha..sup.203 +.alpha..sup.38 =.alpha..sup.87 ( 35) EQU S7=.alpha..sup.95 +.alpha..sup.112 +.alpha..sup.207 +.alpha..sup.43 =.alpha..sup.211 ( 36)
The syndrome polynomial S(z) is given by EQU S(z)=.alpha..sup.224 +.alpha..sup.74 z+.alpha..sup.103 z.sup.2 +.alpha..sup.160 z.sup.3 +.alpha..sup.141 z.sup.4 +.alpha..sup.65 z.sup.5 +.alpha..sup.87 z.sup.6 +.alpha..sup.211 z.sup.7 ( 37)
Since the number of correctable errors t is 4, the Goppa polynomial G(z) is given by EQU G(z)=Z.sup.8 ( 38)
The error locator polynimial .sigma.(z) and the error evaluator polynomial .eta.(z) will be determined using the flowchart of FIG. 13. The initial values are set as follows:
Step 1: EQU Q(z)=.alpha..sup.44 z+.alpha..sup.175 EQU R(z)=.alpha..sup.228 z.sup.6 +.alpha..sup.248 z.sup.5 +.alpha..sup.211 z.sup.4 +.alpha..sup.41 z.sup.3 +.alpha..sup.199 z.sup.2 +.alpha..sup.86 z+.alpha..sup.144 EQU U1(z)=.alpha..sup.44 z+.alpha..sup.175 EQU U2(z)=.alpha..sup.0 EQU deg R(z)=6&gt;t-1=3
The preparation for the next step (hereinafter, the same will be applied) is as follows
Step 2: EQU Q(z)=.alpha..sup.238 z+.alpha..sup.249 EQU R(z)=.alpha..sup.77 z.sup.5 +.alpha..sup.228 z.sup.4 +.alpha..sup.28 z.sup.3 +.alpha..sup.85 z.sup.2 +.alpha..sup.132 z+.alpha..sup.125 EQU U1(z)=.alpha..sup.27 z.sup.2 +.alpha..sup.47 z+.alpha..sup.156 EQU U2(z)=.alpha..sup.44 z+.alpha..sup.175 EQU deg R(z)=5&lt;t-1
Step 3: EQU Q(z)=.alpha..sup.151 z+.alpha..sup.227 EQU R(z)=.alpha..sup.169 z.sup.4 +.alpha..sup.239 z.sup.3 +.alpha..sup.131 z.sup.2 +.alpha..sup.23 z+.alpha..sup.198 EQU U1(z)=.alpha..sup.178 z.sup.3 +.alpha..sup.74 z.sup.2 +.alpha..sup.55 z+.alpha..sup.229 EQU U2(z)=.alpha..sup.27 z.sup.2 +.alpha..sup.47 z+.alpha..sup.156 EQU deg R(z)=4&gt;t-1
Step 4: EQU Q(z)=.alpha..sup.163 z+.alpha..sup.138 EQU R(z)=.alpha..sup.45 z.sup.3 +.alpha..sup.216 z.sup.2 +.alpha..sup.56 z+.alpha..sup.41 EQU U1(z)=.alpha..sup.86 z.sup.4 +.alpha..sup.156 z.sup.3 +.alpha..sup.70 z.sup.2 +.alpha..sup.149 z+.alpha..sup.72 EQU U2(z)=.alpha..sup.178 z.sup.3 +.alpha..sup.74 z.sup.2 +.alpha..sup.55 z+.alpha..sup.229 EQU deg R(z)=3&gt;t-1
At this point, Euclid's algorithm stops operation and the error locator polynomial .sigma.(z) and the error evaluator polynomial .eta.(z) are given by ##EQU20## The error location and value will be determined from the polynomials. The common technique for determining an error location is Chien's algorithm. When the following values,
are substituted in Eq. 18, .sigma.(z)=0, indicating that .alpha..sup.253, .alpha..sup.252, .alpha..sup.251, and .alpha..sup.250 are roots of .sigma.(z) and that the error locations are 3, 4, 5, and 6. Thus, .sigma.(z) becomes EQU .alpha.(z)=(z-.alpha..sup.253)(z-.alpha..sup.252)(z-.sup.251)(z-.alpha..sup .150).
The error values will be determined from the polynomials. The formal differentiation of .sigma.(z) is given by ##EQU21## The error values e3, e4, e5, and e6 for the respective error locations are determined from the polynomials .sigma.(z) and .eta.(z). ##EQU22##
FIG. 14 shows, in block form, a conventional decoder consisting of a multi-stage shift register 109 for delaying the received coded word, an adder 110, a syndrome computation circuit 111, an error locator polynomial deriving circuit 112, a Chien search circuit 113, a synchronizing circuit 114, a sequence control circuit 115, an input terminal 116 for receiving coded words, and an output terminal 117 for sending the corrected information.
In operation, when a coded word is put into the synchronizing circuit 114 through the input terminal 116, the synchronizing circuit detects the head of the received coded word. In response to the detected result, the sequence control circuit 115 starts operation. The received coded word is also put into the syndrome computation circuit 111 and the multi-stage shift register 109. The computed syndrome from the circuit 111 is fed to the error locator polynomial deriving circuit 112 to provide an error locator polynomial, which is then fed to the Chien search circuit 113 for performing Chien search.
As FIG. 15 shows, in the Chien search circuit, the coefficient of each term of the error locator polynomial EQU .sigma.(x)=.sigma.0+.sigma.1x+.sigma.2x.sup.2 + . . . +.sigma.t-1x.sup.t-1
is set in an n-bit register K, to which clock pulses are input. When a certain number of clock pulses are input, the output at the terminal 302 becomes zero. Let the number of clock pulses input is i, then .alpha.i.sup.c is a root of .sigma.(x). This process is called Chien search. At the same time, the received coded word is output from the multi-stage shift register 203 in sequence from the head. This output is synchronized with the Chien search operation performed in the circuit 113. When it is found to be a root of the error locator polynomial .sigma.(x) in the Chien search, the output of the multi-stage shift register 203 is corrected in the correction circuit 206.
FIG. 16 shows a conventional composite circuit having both syndrome and Chien search circuits. In this composite circuit, a syndrome is processed as follows. A succession of 8-bit words received at the input terminal 301 are fed through a switch Sx and the adders A0, A1, . . . A15 in a Galois field GF(2.sup.8) to an array of 8-bit registers L0, L1, . . . L15, which have been cleared, for latching. The latched contents of the registers L1, L2, . . . , L15 are multiplied by constants .alpha., .alpha..sup.2, . . . , .alpha..sup.15 in the Galois field GF(2.sup.8) in the multipliers B1, B2, . . . B15 and fed to the adders A1, A2 . . . A15 for calculating the sums with the next input at the terminal 301. The sums are latched in the registers L1, L2, . . . L15. The content in the register L1 is added to the next input without multiplication in the adder A0 and the sum is latched in the register L0. When all of the received words have been input, the switches Sw0, Sw1, . . . Sw15 are turned to the contacts U so that the calculated syndromes are shifted through the registers L0, L1, . . . L15 in sequence and output at the terminal 303.
The Chien search is performed as follows. The contents of the registers L0, L1, . . . L8 are fed to a summing circuit 304 for providing the sum of the Chien algorithm ##EQU23## at the output terminal 302.
The above conventional decoder has the following shortcomings.
First, since the algorithm for finding error locator and evaluator polynomials completely depends on the program, the process takes much time.
Second, since the received word latched in the multi-stage shift register is corrected on the basis of the error location found in the Chien search circuit, the error locator polynomial deriving circuit becomes complicated for the long coded word, requiring a large number of stages of the multi-stage shift register.
Third, when the code is shortened for process, for example, the locations 148 through 258 are assumed to be 0 and errors up to the location 148 are to be detected for correction, the conventional system will perform calculation for .alpha..sup.-254, .alpha..sup.-253, . . . , .alpha..sup.-148 that are assumed to be 0 and do not actually exist due to the shortened process, thus wasting computing time. If the multiplying circuit is replaced by a dividing circuit and the initial value i=254 is used for computation, the delay time is sufficiently short to eliminate the above shortcoming. However, the dividing circuit is generally more complicated and takes more time in computation than the multiplying circuit.
Fourth, with an encoder which frequently is disposed with the decoder, even the composite circuit having both syndrome and Chien search circuits yet remains to be improved in size.